package priv.conceit.study.leetcode.simple.official;

/**
 * 编号021
 * 合并两个有序链表
 * <a href="https://leetcode-cn.com/problems/merge-two-sorted-lists/"></a>
 * 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 示例：
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 * <p>
 * <p>
 * 思路：
 * 递归
 * <p>
 * 前置条件：
 * 两个链表都不能为空
 * <p>
 * 递归内容：
 * l1和l2 的哪一个val更小，小的放前面
 *
 * 递归返回：
 * 已经排好序的链标头
 *
 * 终止条件：
 * l1或者l2 为空时结束
 *
 * @author: conceit
 * @date: 2019/7/5 15:53
 */
public class MergeTwoSortedLists {



	public static void main(String[] args) {

		ListNode l1=new ListNode(1,new ListNode(3));
		ListNode l2=new ListNode(0,new ListNode(2));
		ListNode l3=new MergeTwoSortedLists().mergeTwoLists(l1,l2);
		print(l3);

	}
	public static class ListNode {
		int val;

		ListNode next;

		public ListNode(int x) {
		val = x;
		}


	public ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
	}

	}

	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

		if (l1 == null && l2 == null) {
			return null;
		}
		ListNode head;

		//头节点 存放每次保存的链表

		//递归至最后必定有一个链表先完成
		//只需要将将已经作为主线的链表返回就完事
		if(l1==null){
			return l2;
		}
		if(l2==null){
			return l1;
		}
		print(l1);
		print(l2);
		if(l1.val<=l2.val){
			//用l1的下一个节点继续比较和l2进行比较
			//此时l1作为主线
			l1.next=mergeTwoLists(l1.next,l2);
			return l1;
		}else{
			//此时l2作为主线
			l2.next=mergeTwoLists(l1,l2.next);
			return l2;
		}

	}

	public static void print(ListNode listNode){
		System.out.println("--------------");
		ListNode culNode=listNode;
		while (true){
			if(culNode!=null){
				System.out.println(culNode.val);
				culNode=culNode.next;
			}else{
				break;
			}

		}
		System.out.println("--------------");
	}
}
